package fibonacci

// 思路：用a存储较小数，用b存储较大数，
// 通过循环来计算斐波那契数列
// 复杂度：O(n)
// 空间复杂度：O(1)
// 斐波那契数列
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
// 第一次 a=0 b=1 相加=1赋值给a,b=1 n=2
// 第二次 a=1 b=1 相加=2赋值给a,b=1 n=3
// 第三次 a=2 b=1 相加=3赋值给a,b=2 n=4
// 第四次 a=3 b=2 相加=5赋值给a,b=3 n=5
// 第五次 a=5 b=3 相加=8赋值给a n=6
// 第六次 a=8 b=5 相加=13赋值给a n=7
// 第七次 a=13 b=8 相加=21赋值给a n=8
// 第八次 a=21 b=13 相加=34赋值给a n=9
func fib(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	a, b := 0, 1
	for i := 1; i < n; i++ {
		a, b = b, a+b // 下一次a用b的值，b用a+b的值
	}
	return b
}

// 递归实现
// 复杂度：O(2^n)
// 空间复杂度：O(n)
func fib_recursive(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	return fib_recursive(n-1) + fib_recursive(n-2)
}

// 记忆化递归实现
// 复杂度：O(n)
// 空间复杂度：O(n)
func fib_memoization(n int) int {
	memo := make(map[int]int)
	var fibHelper func(int) int
	fibHelper = func(n int) int {
		if n == 0 {
			return 0
		}
		if n == 1 {
			return 1
		}
		if val, ok := memo[n]; ok {
			return val
		}
		memo[n] = fibHelper(n-1) + fibHelper(n-2)
		return memo[n]
	}
	return fibHelper(n)
}

// 动态规划实现
// 复杂度：O(n)
// 空间复杂度：O(n)
func fib_dynamic(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

// 动态规划优化实现
// 复杂度：O(n)
// 空间复杂度：O(1)
func fib_dynamic_optimized(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	a, b := 0, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}
